package LeetCode_力扣;

/** 82. 删除排序链表中的重复元素 II
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，
 * 只留下不同的数字 。返回 已排序的链表 。
 */

/**
 * 思路：要求是重复节点一个都不留，我们之前单链表的删除都是通过
 * 前驱节点删除 =》 现在第一个节点就有可能会是重复节点了，
 * 要保证 prve 坚决不能能带删除的节点，我们可以引用
 * 虚拟头节点的概念，如果不增加一个空节点来做，那么题目会变的非常的复制难办。
 * 但现在我们还需要 两个指针来判断是否为 重复数，那就再引入 node1，node2
 */
//public class deleteDuplicates_82 {
//    public ListNode deleteDuplicates(ListNode head) {
//
//        //当链表为空或者 只有一个是时候，肯定没有重复元素
//        if(head == null || head.next == null){
//            return head;
//        }
//        //此时说明至少有两个节点，可能存在重复数
//        ListNode dummyHead = new ListNode();
//        //连接一下
//        dummyHead.next = head;
//        //prve来引领虚拟头节点来走正确，不是重复数的节点。
//        ListNode prve = dummyHead;
//        //用两个指针来判断是否为重复数
//        ListNode node1 = prve.next;
//        ListNode node2 = node1.next;
//
//        while(node2 != null){
//
//            if(node1.val == node2.val){
//                //既然这两个数是重复数，肯定要
//                //更新prve执行的地址，至少是它们两个数的下一个节点地址
//                while( node2 != null && node1.val == node2.val ){
//                    node2 = node2.next;
//                }//走到不是刚遇到的重复数的时候停下来
//                prve.next = node2;
//                //判断一下node2是否走到头了
//                if(node2 == null)
//                    return dummyHead.next;
//            }else{
//                //如果他们都不是重复的数
//                //移动prve的位置
//                prve = node1;
//            }
//            node1 = node2;
//            node2 = node2.next;
//        }
//        return dummyHead.next;
//    }
//
//}

/**
 * 递归写法：功能是删除链表里面所有重复的元素，返回新链表的头
 */

/**
 * 思路：我们要做的是 必须保证头节点不是待删除元素，然后把头节点不是待删除链表
 * 交给子方法去处理，让它完成里面的重复删除。
 */

//public class deleteDuplicates_82 {
//    public ListNode deleteDuplicates(ListNode head) {
//
//        //什么情况下不用删除了？
//        if(head == null || head.next == null){
//            //为空，或者只有一个节点，那肯定没有重复数啊
//            return head;
//        }
//        //判断头节点是否是待删除节点
//        if(head.val != head.next.val){
//            head.next = deleteDuplicates(head.next);
//            return head;//因为第一个不是待删除节点，所以可以直接连接
//        }else{
//            //重点！如果是带删除节点的话 ，先处理掉
//            //注释：我们只需要做到删除头节点带删数，至于后面的数里面有没有头节点交给方法去执行
//            ListNode node = head.next;
//            while(node != null && head.val == node.val){
//                //重复的话就一直让node往后走
//                node = node.next;
//            }//循环完后node跟第一个头节点val相比，肯定不相同。
//            //node是新的头节点，至于这个头节点是否需要删除，就交给子方法
//            return deleteDuplicates(node);
//
//        }
//
//    }
//}

//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode() {
//    }
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}